struct SCC
{
    int n;
    vector<vector<int>> e, e1;
    vector<int> dfn, low, stk, id, sz;
    int cnt, now;
    SCC() {}
    SCC(int n)
    {
        init(n);
    }
    void init(int n)
    {
        this->n = n;
        e.assign(n + 1, {});
        dfn.assign(n + 1, -1);
        low.resize(n + 1);
        id.assign(n + 1, -1);
        sz.assign(n + 1, 0);
        cnt = now = 0;
        stk.clear();
    }
    void add(int u, int v)
    {
        e[u].push_back(v);
    }
    void dfs(int u)
    {
        dfn[u] = low[u] = ++now;
        stk.push_back(u);
        for (auto v : e[u])
        {
            if (dfn[v] == -1)
            {
                dfs(v);
                low[u] = min(low[u], low[v]);
            }
            else if (id[v] == -1)
            {
                low[u] = min(low[u], low[v]);
            }
        }
        if (dfn[u] == low[u])
        {
            cnt++;
            int y;
            do
            {
                y = stk.back();
                id[y] = cnt;
                sz[cnt]++;
                stk.pop_back();
            } while (y != u);
        }
        return;
    }
    vector<int> work()
    {
        for (int i = 1; i <= n; i++)
        {
            if (dfn[i] == -1)
            {
                dfs(i);
            }
        }
        return id;
    }
    vector<vector<int>> rebuild()
    {
        vector e1(cnt + 1, vector<int>());
        for (int i = 1; i <= n; i++)
        {
            for (auto v : e[i])
            {
                if (id[v] != id[i])
                {
                    e1[id[i]].push_back(id[v]);
                }
            }
        }
        return e1;
    }
    int Len()
    {
        return cnt;
    }
};